package com.study.daily.algozuo.y2021.m12.day1209;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2021/12/9 下午 07:57
 * @version: 1.0
 */
public class Code03_Bags {
    /**
     * weights[i], values[i], 代表的是重量和價值
     * bags 背包的容量
     * 在背包容量範圍内的最大值
     */
    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7, 3, 1, 7};
        int[] values = {5, 6, 3, 19, 12, 4, 2};
        int bag = 20;
        System.out.println(bags1(weights, values, bag));
        System.out.println(bags2(weights, values, bag));
        System.out.println(bags3(weights, values, bag));
    }

    public static int bags1(int[] weights, int[] values, int bag) {
        int N = weights.length;
        return process1(weights, values, bag, 0);
    }

    public static int process1(int[] weights, int[] values, int rest, int index) {
        if (rest < 0) {
            return -1;
        }
        if (index == weights.length) {
            return 0;
        }
        int p1 = process1(weights, values, rest, index + 1);
        int p2 = 0;
        int next = process1(weights, values, rest - weights[index], index + 1);
        if (next != -1) {
            p2 = values[index] + next;
        }
        return Math.max(p1, p2);
    }

    public static int bags2(int[] weights, int[] values, int bag) {
        int N = weights.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < bag + 1; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(weights, values, bag, 0, dp);
    }

    public static int process2(int[] weights, int[] values, int rest, int index, int[][] dp) {
        if (rest < 0) return -1;

        if (dp[index][rest] != -1) {
            return dp[index][rest];
        }
        if (index == weights.length) {
            dp[index][rest] = 0;
            return 0;
        }
        // 如果不要index位置
        int p1 = process2(weights, values, rest, index + 1, dp);
        int p2 = 0;
        int next = process2(weights, values, rest - weights[index], index + 1, dp);
        if (next != -1) {
            p2 = next + values[index];
        }
        dp[index][rest] = Math.max(p1, p2);
        return Math.max(p1, p2);
    }

    public static int bags3(int[] weights, int[] values, int bag) {
        int N = weights.length;
        int[][] dp = new int[N + 1][bag + 1];
        for (int j = 0; j <= bag; j++) {
            dp[N][j] = 0;
        }
        for (int i = N - 1; i >= 0; i--) {
            for (int j = 0; j < bag + 1; j++) {
                int p1 = dp[i + 1][j];
                int p2 = 0;
                int next = j - weights[i] < 0 ? -1 : dp[i + 1][j - weights[i]];
                if (next != -1) {
                    p2 = values[i] + next;
                }
                dp[i][j] = Math.max(p1, p2);
            }
        }
        return dp[0][bag];
    }
}
